package com.lin.codesnippet.sort;

import com.lin.enums.codesnippet.SortStatusCode;
import com.lin.codesnippet.sort.util.SortUtil;

/**
 * 希尔排序
 * <p>O(n^1.3)~O(nlogn)~O(n^2)~O(n^2)</p>
 * 不稳定
 *
 * @author linqiankun
 */
public class ShellSort {


    /**
     * 希尔排序
     *
     * @param array 需要排序的数组
     * @param sortStatusCode 排序方式
     */
    public static void shellSorted(int[] array, SortStatusCode sortStatusCode) {
        int shell = 0;
        //寻找最大的希尔值
        while (shell <= array.length) {
            shell = shell * 3 + 1;
        }
        //通过希尔来降低排序复杂度
        while (shell >= 1) {
            //确定希尔值后，内部使用呢直接插入排序
            for (int i = shell; i < array.length; i++) {
                int j = i - shell;
                int get = array[i];
                while (j >= 0 && sortStatusCode.getCode() == SortUtil.compare(get, array[j])) {
                    array[j + shell] = array[j];
                    j = j - shell;
                }
                array[j + shell] = get;
            }
            shell = (shell - 1) / 3;
        }


    }

}
